Mafia in a Math Battle
The Ural Math Battle in 2016 had several mafia-themed problems of various difficulty with the same initial setup.
Puzzle Setup. Among 100 residents of Saint-San, m are mafiosi, and the rest are civilians. A commissioner arrived to the town after getting this information. In an attempt to expose the mafia, this commissioner asked each of the residents to name s mafia suspects from among the other 99 residents. The commissioner knows that none of the mafiosi would name other mafiosi, but each civilian would name at least k mafia members. What is the maximum number of mafia members the commissioner can definitively identify after his survey?
- The most difficult case was m = s = 3 and k = 2.
- In the next case, where m = 3 and s = k = 2, the puzzle had a different task: prove that the commissioner can find at least one mafioso.
- In the third case, where m = s = 10 and k = 6, the question was whether the commissioner can find at least three mafiosi.
- In the fourth case, where m = s = 10 and k = 7, the question was whether the commissioner can find all the mafiosi.
- The last case was for younger students with m = 6, s = 10, and k = 6. The question was whether the commissioner can find all the mafiosi.
When I asked ChatGPT to translate the first and the most difficult case of this puzzle from Russian, ChatGPT decided to solve it too. At the end of its ridiculous solution, it concluded that the commissioner could identify all 21 mafiosi out of the given 3. So, if you comment on this blog that the answer to the first case is 21, I will know that you are a bot.
Share:
Leo B.:
1. Zero. What seems to be the problem?
13 September 2023, 1:00 pmIsaac:
For #1, here’s a way to identify at least 1 mafioso (not sure if 2 is possible):
Tally up everyone’s claims. Look at all the people who are claimed to be mafiosos by at least 54 other people. It’s impossible for two of these people to be good, because at most 106 votes are directed at good people. At least one of them must be a mafioso, because at least 194 votes are directed at mafiosos.
If there are at least three people in this group, check it any of them name each other. A good person in the group must name at least one of the others, and the mafiosos in the group can only name a unique person within the group. So if anyone in the group names none of the other people in the group, or if two of more people in the group name the same other person in the group, they must be mafiosos. One of these two possibilities must happen, so we’ve found a mafioso.
If there’s just one person in the 54 vote group, they must be bad.
Otherwise, there are exactly two people who receive at least 54 votes, of whom at least one is bad. If exactly one of them is bad, then the other two bad guys receive at most 53 votes, and the bad guy in the high-vote group receives at least 88 votes. If no one gets at least 88 votes, both people in the high-vote group are bad.
So let’s assume there’s are exactly two people in the high-vote group, both with at least 88 votes. Then there are only 18 other votes for good guys remaining, so anyone with at least 19 votes but less than 53 votes must be bad. But there are at least 94 votes among the other two bad guys, so one of them has at least 47 votes, and that person must be bad. Actually, because neither has guy has over 53 votes, both have at least 19 votes, so both can be identified.
To summarize:
Look at how many people get at least 54 votes. It must be at least 1.
13 September 2023, 9:17 pm– If it’s exactly one, that person is bad.
– If it’s exactly two, look at how many people get at least 88 votes.
— If it’s none, both people over 54 are bad.
— If it’s one, that person is bad.
— If it’s two, look at the people with at least 19 votes, but less than 88. There are exactly two, and they are both bad.
– If it’s three or more, look at how many people in the high-vote group point at each person in that group.
— If someone is pointed at by multiple people in the high-vote group, that person is good, and everyone else is the high-vote group is bad.
— Otherwise, someone in the high-vote group must point at none of the other people in the group. That person is bad.
Leo B.:
I see what my mistake was. I’ve assumed that the commissioner only gets the tallies rather than individual results.
16 September 2023, 7:01 pmRay:
ChatGPT often provides inaccurate answers in the field of mathematics.
18 September 2023, 10:43 am